﻿namespace LeetCode
{
    /*
     215. 数组中的第K个最大元素
    中等
    2.1K
    相关企业
    给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

    请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

    你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

 

    示例 1:

    输入: [3,2,1,5,6,4], k = 2
    输出: 5
    示例 2:

    输入: [3,2,3,1,2,4,5,5,6], k = 4
    输出: 4
 

    提示：

    1 <= k <= nums.length <= 105
    -104 <= nums[i] <= 104
     */
    public class Solution215
    {
        public int FindkthLargest(int[] nums,int k)
        {
            var btree=new BTree();
            foreach(var _ in nums)
            {
                btree.Add(_);
            }
            var result = btree.KthLargest(k);
            return result;
        }
    }
    internal class TreeNode
    {
        public TreeNode? Parent;
        public TreeNode? LeftChild;
        public TreeNode? RightChild;
        public int val;
    }
    /// <summary>
    /// 二叉树，节点的左孩子节点小于当前节点值，右孩子节点大于等于当前节点值
    /// </summary>
    internal class BTree
    {
        private int _count;
        public int Count { get { return _count; } }
        private TreeNode _root;
        public TreeNode Root
        {
            get { return _root; }
            private set { _root = value; }
        }
        private TreeNode _largestNode;
        public TreeNode LargestNode 
        { 
            get { return _largestNode; }
            private set { _largestNode = value;}
        }
        public bool Any()
        {
            return Root != null;
        }
        public void Add(int val)
        {
            if(Root==null)
            {
                _root = new TreeNode() { val=val };
                LargestNode= _root;
            }
            else
            {
                DoAdd(_root,val);
            }
            _count++;
        }
        private void DoAdd(TreeNode currentNode,int val)
        {
            if(val < currentNode.val)
            {
                if(currentNode.LeftChild== null)
                {
                    currentNode.LeftChild = new TreeNode()
                    {
                        val = val,
                        Parent= currentNode,
                    };
                }
                else
                {
                    DoAdd(currentNode.LeftChild,val);
                }
                
                
            }
            else
            {
                //
                // val >= currentNode.val
                if(currentNode.RightChild== null)
                {
                    currentNode.RightChild = new TreeNode()
                    {
                        val = val,
                        Parent= currentNode,
                    };
                    if (currentNode.RightChild.val >= _largestNode.val)
                    {
                        _largestNode = currentNode.RightChild;
                    }
                }
                else
                {
                    DoAdd(currentNode.RightChild,val);
                }
                               
            }
        }
        public int KthLargest(int k)
        {
            if(LargestNode==null || k < 0)
            {
                return -1;
            }
            return DoKthLargest(LargestNode,k);
        }
        private int DoKthLargest(TreeNode largestNode,int k)
        {

            if(k==1)
            {
                return largestNode.val;
            }
            else
            {
                if (largestNode.LeftChild != null)
                {
                    if(largestNode.LeftChild.RightChild!=null)
                    {
                        return DoKthLargest(largestNode.LeftChild.RightChild,k-1);
                    }
                    else
                    {
                        return DoKthLargest(largestNode.LeftChild, k - 1);
                    }                  
                }
                if (largestNode.Parent != null && largestNode.Parent.RightChild==largestNode )
                {
                    return DoKthLargest(largestNode.Parent, k - 1);                   
                }                              
            }
            return -1;
        }
    }
}
